/*
 * @Description: 分离链接
 * @Autor: wangxin
 * @Date: 2020-06-13 22:28:12
 * @LastEditTime: 2020-06-13 23:50:40
 */
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}
class LinkedList {
  constructor() {
    this.count = 0
    this.head = null
  }

  /**
   * 向链表尾部添加新元素
   */
  push(element) {
    const node = new Node(element)
    let current
    if (this.head == null) {
      this.head = node
    } else {
      current = this.head
      // 获得最后一项
      while (current.next != null) {
        current = current.next
      }
      // 将next赋为新元素，建立链接
      current.next = node
    }

    this.count++
  }
  /**
   * 循环迭代链表直到目标位置
   */
  getElementAt(index) {
    if (index < 0 || index >= this.count) {
      return undefined
    }
    let current = this.head
    for (let i = 0; i < index; i++) {
      current = current.next
    }
    return current
  }
  /**
   * 从链表中特定位置移除一个元素
   */
  removeAt(index) {
    // 检查越界值
    if (index < 0 || index >= this.count) {
      return undefined
    }
    let current = this.head
    // 移除第一项
    if (index === 0) {
      this.head = current.next
    } else {
      const previous = this.getElementAt(index - 1)
      // 需要被移除的项
      current = previous.next
      // 跳过current，从而移除它
      previous.next = current.next
    }
    this.count--
    return current.element
  }
  /**
   * 在任意位置插入元素
   */
  insert(element, index) {
    // 检查越界值
    if (index < 0 || index > this.count) {
      return false
    }
    const node = new Node(element)

    // 在第一个位置插入元素
    if (index === 0) {
      const current = this.head
      node.next = current
      this.head = node
    } else {
      // 插入新元素的前一个元素
      const previous = this.getElementAt(index - 1)
      // 插入新元素的后一个元素
      const current = previous.next
      node.next = current
      previous.next = node
    }
    this.count++
    return true
  }
  /**
   * 返回一个元素的位置，没有找到返回-1
   */
  indexOf(element) {
    let current = this.head

    for (let i = 0; i < this.count; i++) {
      if (current.element == element) {
        return i
      }
      current = current.next
    }
    // 没有找到
    return -1
  }
  /**
   * 把链表转换成一个字符串
   */
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`
    let current = this.head.next
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${current.element}`
      current = current.next
    }
    return objString
  }
  /**
   * 从链表中移除元素
   */
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }
  /**
   * 判断链表是否有元素
   */
  isEmpty() {
    return this.count === 0
  }
  /**
   * 返回链表的长度
   */
  size() {
    return this.count
  }
  /**
   * 返回链表的头部元素
   */
  getHead() {
    return this.head
  }
}
class ValuePair {
  constructor(key, value) {
    this.key = key
    this.value = value
  }
  toString() {
    return `[${this.key}:${this.value}]`
  }
}

class HashTableSeparateChaining {
  constructor(toStrFn = this.defauiltToString) {
    this.toStrFn = toStrFn
    this.table = {}
  }

  defauiltToString(item) {
    if (item === null) {
      return 'NULL'
    } else if (item === undefined) {
      return 'UNDEFINED'
    } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`
    }
    return item.toString()
  }

  loseHashCode(key) {
    if (typeof key === 'number') {
      return key
    }
    const tableKey = this.toStrFn(key)
    let hash = 0
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i)
    }
    return hash % 37
  }

  hashCode(key) {
    return this.loseHashCode(key)
  }

  size() {
    return Object.keys(this.table).length
  }

  isEmpty() {
    return this.size() === 0
  }

  toString() {
    if (this.isEmpty()) {
      return ''
    }
    const keys = Object.keys(this.table)
    let objStrng = `{${keys[0]}--${this.table[keys[0]].toString()}}`
    for (let i = 1; i < keys.length; i++) {
      objStrng = `${objStrng},${keys[i]}--${this.table[keys[i]].toString()}`
    }
    return objStrng
  }

  put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key)
      if (this.table[position] == null) {
        this.table[position] = new LinkedList()
      }
      this.table[position].push(new ValuePair(key, value))
      return true
    }
    return false
  }

  get(key) {
    const position = this.hashCode(key)
    const linkedList = this.table[position]
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead()
      while (current != null) {
        if (current.element.key === key) {
          return current.element.value
        }
        current = current.next
      }
    }
    return undefined
  }

  remove(key) {
    const position = this.hashCode(key)
    const linkedList = this.table[position]
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead()
      while (current != null) {
        if (current.element.key === key) {
          linkedList.remove(current.element)
          if (linkedList.isEmpty()) {
            delete this.table[position]
          }
          return true
        }
        current = current.next
      }
    }
    return false
  }
}

const hash = new HashTableSeparateChaining()
hash.put('Nathan', 'Nathan.com')
hash.put('Sargeras', 'Sargeras.com')

hash.put('Jack', 'Jack.com')
hash.put('Athelstan', 'Athelstan.com')

hash.put('Jamie', 'Jamie.com')
hash.put('Sue', 'Sue.com')

console.log(hash.remove('Jack'))
console.log(hash.toString())
